// levels.js - 优化版推箱子关卡系统

// 性能优化：使用WeakMap进行缓存，避免内存泄漏
const reachabilityCache = new WeakMap();

// 性能优化：预定义常用方向和常量
const DIRECTIONS = Object.freeze([
    { dx: 0, dy: -1 }, // 上
    { dx: 0, dy: 1 },  // 下
    { dx: -1, dy: 0 }, // 左
    { dx: 1, dy: 0 }   // 右
]);

const CELL_TYPES = Object.freeze({
    EMPTY: 0,
    WALL: 1,
    BOX: 2,
    TARGET: 3,
    PLAYER: 4,
    BOX_ON_TARGET: 5
});

// 性能优化：使用位运算替代对象深拷贝
function cloneMap(map) {
    return map.map(row => new Uint8Array(row));
}

// 高效洗牌算法 (Fisher-Yates)
function shuffleArray(array) {
    for (let i = array.length - 1; i > 0; i--) {
        const j = Math.floor(Math.random() * (i + 1));
        [array[i], array[j]] = [array[j], array[i]];
    }
    return array;
}

// 带缓存的路径可达性检查 (BFS)
function canPlayerReach(map, startPos, targetPos) {
    // 性能优化：使用坐标哈希作为缓存键
    const cacheKey = `${startPos.x},${startPos.y}|${targetPos.x},${targetPos.y}`;

    if (!reachabilityCache.has(map)) {
        reachabilityCache.set(map, new Map());
    }

    const mapCache = reachabilityCache.get(map);
    if (mapCache.has(cacheKey)) {
        return mapCache.get(cacheKey);
    }

    const height = map.length;
    const width = map[0].length;
    const visited = new Array(height);
    for (let i = 0; i < height; i++) {
        visited[i] = new Uint8Array(width);
    }

    const queue = [startPos];
    visited[startPos.y][startPos.x] = 1;

    while (queue.length > 0) {
        const { x, y } = queue.shift();

        // 到达目标位置
        if (x === targetPos.x && y === targetPos.y) {
            mapCache.set(cacheKey, true);
            return true;
        }

        // 检查四个方向
        for (const dir of DIRECTIONS) {
            const nx = x + dir.dx;
            const ny = y + dir.dy;

            // 边界检查
            if (nx >= 0 && ny >= 0 && nx < width && ny < height) {
                // 可通行且未访问
                if (map[ny][nx] !== CELL_TYPES.WALL && !visited[ny][nx]) {
                    visited[ny][nx] = 1;
                    queue.push({ x: nx, y: ny });
                }
            }
        }
    }

    mapCache.set(cacheKey, false);
    return false;
}

// 检查箱子移动可能性
function canBoxBeMovedTo(map, boxPos, targetPos, playerPos) {
    // 目标位置必须是空地或目标点
    if (map[targetPos.y][targetPos.x] === CELL_TYPES.WALL) {
        return false;
    }

    // 计算移动方向
    const dx = targetPos.x - boxPos.x;
    const dy = targetPos.y - boxPos.y;

    // 只能直线推箱子
    if (dx !== 0 && dy !== 0) return false;

    // 确定推动方向
    const pushDir = dx !== 0
        ? (dx > 0 ? { dx: 1, dy: 0 } : { dx: -1, dy: 0 })
        : (dy > 0 ? { dy: 1, dx: 0 } : { dy: -1, dx: 0 });

    // 玩家需要站在反方向的位置
    const playerPushPos = {
        x: boxPos.x - pushDir.dx,
        y: boxPos.y - pushDir.dy
    };

    return canPlayerReach(map, playerPos, playerPushPos);
}

// 改进的关卡可解性检查
function isLevelSolvable(level) {
    // 性能优化：使用类型化数组
    const map = cloneMap(level.map);
    const boxes = [...level.boxes];
    const targets = [...level.targets];
    const playerPos = { ...level.playerPos };

    // 检查玩家是否能到达每个箱子
    for (const box of boxes) {
        if (!canPlayerReach(map, playerPos, box)) {
            return false;
        }
    }

    // 检查每个箱子是否能到达至少一个目标点
    for (const box of boxes) {
        let canReachTarget = false;
        for (const target of targets) {
            if (canBoxBeMovedTo(map, box, target, playerPos)) {
                canReachTarget = true;
                break;
            }
        }
        if (!canReachTarget) return false;
    }

    return true;
}

// 智能关卡生成器
class LevelGenerator {
    static DIFFICULTY_SETTINGS = {
        easy: {
            size: { width: 8, height: 8 },
            wallRatio: 0.15,
            boxes: { min: 1, max: 2 }
        },
        medium: {
            size: { width: 10, height: 10 },
            wallRatio: 0.2,
            boxes: { min: 3, max: 4 }
        },
        hard: {
            size: { width: 12, height: 12 },
            wallRatio: 0.25,
            boxes: { min: 5, max: 6 }
        }
    };

    static generate(difficulty) {
        const settings = this.DIFFICULTY_SETTINGS[difficulty];
        if (!settings) throw new Error('Invalid difficulty level');

        const { width, height } = settings.size;
        const numWalls = Math.floor(width * height * settings.wallRatio);
        const numBoxes = Math.floor(
            Math.random() * (settings.boxes.max - settings.boxes.min + 1)
        ) + settings.boxes.min;

        // 创建地图
        const map = Array(height).fill().map(() => new Uint8Array(width).fill(CELL_TYPES.EMPTY));

        // 添加外围墙壁
        for (let y = 0; y < height; y++) {
            map[y][0] = map[y][width - 1] = CELL_TYPES.WALL;
        }
        for (let x = 0; x < width; x++) {
            map[0][x] = map[height - 1][x] = CELL_TYPES.WALL;
        }

        // 生成内部墙壁
        const availablePositions = [];
        for (let y = 1; y < height - 1; y++) {
            for (let x = 1; x < width - 1; x++) {
                availablePositions.push({ x, y });
            }
        }
        shuffleArray(availablePositions);

        for (let i = 0; i < numWalls; i++) {
            const { x, y } = availablePositions[i];
            map[y][x] = CELL_TYPES.WALL;
        }

        // 生成玩家位置
        const playerPos = this.findValidPosition(map, availablePositions, numWalls);
        map[playerPos.y][playerPos.x] = CELL_TYPES.PLAYER;

        // 生成目标点
        const targets = [];
        for (let i = 0; i < numBoxes; i++) {
            const targetPos = this.findValidPosition(
                map,
                availablePositions,
                numWalls + i,
                pos => !targets.some(t => this.manhattanDistance(t, pos) < 3)
            );
            map[targetPos.y][targetPos.x] = CELL_TYPES.TARGET;
            targets.push(targetPos);
        }

        // 生成箱子
        const boxes = [];
        for (let i = 0; i < numBoxes; i++) {
            const boxPos = this.findValidPosition(
                map,
                availablePositions,
                numWalls + numBoxes + i,
                pos => !boxes.some(b => this.manhattanDistance(b, pos) < 3) &&
                    !targets.some(t => this.manhattanDistance(t, pos) < 2)
            );
            map[boxPos.y][boxPos.x] = CELL_TYPES.BOX;
            boxes.push(boxPos);
        }

        return {
            id: Date.now(),
            name: `${difficulty} Level`,
            map,
            playerPos,
            boxes,
            targets,
            difficulty
        };
    }

    static findValidPosition(map, positions, offset = 0, validator = () => true) {
        for (let i = offset; i < positions.length; i++) {
            const pos = positions[i];
            if (map[pos.y][pos.x] === CELL_TYPES.EMPTY && validator(pos)) {
                return pos;
            }
        }
        // 回退策略：返回第一个可用位置
        for (const pos of positions) {
            if (map[pos.y][pos.x] === CELL_TYPES.EMPTY) {
                return pos;
            }
        }
        throw new Error('No valid position found');
    }

    static manhattanDistance(a, b) {
        return Math.abs(a.x - b.x) + Math.abs(a.y - b.y);
    }
}

// 预生成关卡池
const LEVEL_POOL = {
    easy: [],
    medium: [],
    hard: []
};

// 初始化关卡池
function initializeLevelPool() {
    // 预生成简单关卡
    for (let i = 0; i < 10; i++) {
        const level = LevelGenerator.generate('easy');
        if (isLevelSolvable(level)) {
            LEVEL_POOL.easy.push(level);
        }
    }

    // 预生成中等难度关卡
    for (let i = 0; i < 10; i++) {
        const level = LevelGenerator.generate('medium');
        if (isLevelSolvable(level)) {
            LEVEL_POOL.medium.push(level);
        }
    }

    // 预生成困难关卡
    for (let i = 0; i < 10; i++) {
        const level = LevelGenerator.generate('hard');
        if (isLevelSolvable(level)) {
            LEVEL_POOL.hard.push(level);
        }
    }
}

// 获取关卡
function getLevel(difficulty, index) {
    const pool = LEVEL_POOL[difficulty];
    if (!pool || pool.length === 0) {
        throw new Error(`No ${difficulty} levels available`);
    }
    return pool[index % pool.length];
}

// 初始化关卡系统
initializeLevelPool();

// 预生成的关卡数组
const LEVELS = (() => {
    const levels = [];
    // 生成5个简单关卡
    for (let i = 0; i < 5; i++) {
        levels.push(LevelGenerator.generate('easy'));
    }
    // 生成3个中等关卡
    for (let i = 0; i < 3; i++) {
        levels.push(LevelGenerator.generate('medium'));
    }
    // 生成2个困难关卡
    for (let i = 0; i < 2; i++) {
        levels.push(LevelGenerator.generate('hard'));
    }
    return levels;
})();

// 导出接口
export {
    CELL_TYPES,
    getLevel,
    canPlayerReach,
    canBoxBeMovedTo,
    isLevelSolvable,
    LEVELS
};
